// m

// 给定一个二叉树，要求找到该树中指定节点p，q的最近公共祖先
// 祖先：若节点p在节点node的左子树或右子树中，或者p = node，则称node是p的祖先
// 最近公共祖先：对于树的两个节点p、q，最近公共祖先表示为一个节点lca_node，满足lca_node是p、q的祖先且lca_node的深度尽可能大

// 解题思路：
// 若lca_node是节点p、q的最近公共祖先，则lca_node只能是下面几种情况：
// 1. p、q在lca_node的子树中，且分别在lca_node的两侧子树中
// 2. p = lca_node,且q在lca_node的左子树或者右子树中
// 3. q = lca_node,且p在lca_node的左子树或者右子树中

function lowestCommonAncestor(root, p, q) {
    if (root === p || root === q) {
        return root
    }
    if (root) {
        let node_left = lowestCommonAncestor(root.left, p, q)
        let node_right = lowestCommonAncestor(root.right, p, q)
        if (node_left && node_right) {
            return root
        } else if (!node_left) {
            return node_right
        } else {
            return node_left
        }
    }
    return null
}

let q = {
    val: 'q',
    left: null,
    right: null
}

let p = {
    val: 'p',
    left: null,
    right: null
}
const root = {
    val: 1,
    left: {
        val: 2,
        left: q,
        right: {
            val: 9,
            right: p,
            left : null

        }
    },
    right: {
        val: 22,
        left: null,
        right: null
    },
};

console.log(lowestCommonAncestor(root, p, q))